'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-26 10:24:29
'''
'''
113. 路径总和 II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

tips:简单递归，需要注意的是题目，到叶子节点。然后记着如果append了，在return之前一定要pop
'''

from tree_node import *
from typing import List
import copy
class Solution:
    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        path = []
        ans = []
        def recurse(root):
            if not root:
                return
            path.append(root.val)
            # print(path)
            if not root.left and not root.right and sum(path)==target:
                ans.append(copy.copy(path))
                path.pop()
                return
            recurse(root.left)
            recurse(root.right)
            path.pop()
        
        recurse(root)
        return ans
            
if __name__ == "__main__":
    solution = Solution()
    null = 'null'
    root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
    for i,v in enumerate(root):
        root[i] = str(v)
    s = ','.join(root)
    # print(s)
    o_s = OfficialSerialize()
    root = o_s.deserialize(s)
    target=16
    print(solution.pathSum(root, 16))